1. Field of the Invention
This invention is related to the field of caches and, more particularly, to replacement policies in caches.
2. Description of the Related Art
Various components in a system may access system memory. For example, processors executing software may access memory to read the instructions that form the software and to access data that the instructions are manipulating. Fixed function components can also access memory (e.g. direct memory access (DMA) controllers, peripheral interface controllers on behalf of peripheral components, etc.). Generally, the system memory is constructed to maximize capacity without unduly lengthening latency. However, the latency to system memory may still be a significant factor limiting the performance of various components.
To reduce effective memory latency, system components may include caches or may be coupled to caches. For example, processors often include caches and may also be coupled to additional external caches in a cache memory hierarchy. Typically, caches can provide low latency access to a subset of the data that is also stored in the system memory. For example, caches can be hardware-managed memories that store recently accessed data, and the cache management hardware writes copies of data accessed by the processors to the cache. Similarly, caches to which other memory-reading components are coupled may write data accessed by such components to the cache. Data that has been modified can be replaced in the cache by newer data, and the cache management hardware can write the modified data back to the main memory. In some cases, the processors can include prefetch instructions and other cache hints to influence the operation of the cache management hardware and can mark memory non-cacheable to prevent caching, but generally software cannot control the cache management hardware.
One mechanism managed by the cache management hardware is the replacement of cached data when a cache miss occurs. There are various replacement policies that can be implemented to select cached data to be replaced. Each replacement policy is beneficial for some access patterns, and not as beneficial for others. Typically, the cache designer selects a replacement policy that is expected to perform best under expected work loads and that is expected to be implementable within the timing constraints of the design, and implements that replacement policy.